This invention relates to an image data coding apparatus for compressing image data, an image data reconstructing method and an apparatus for reconstructing images from compressed data. More particularly, it relates to a coding apparatus for coding continuous tone images, after dividing them into blocks each comprising a plurality of picture elements, by orthogonally transforming the picture elements in respective blocks, and to an image data reconstructing method and apparatus for reconstructing images from the orthogonally transformed coded data.
Gradient values for respective picture elements need to be coded highly efficiently, for storing or transmitting, at high speed and high quality, image data, especially grayscale image data and color image data, whose information volume is exceedingly greater than that of coded numerical data.
Conventionally, an adaptive discrete cosine transform coding method is used as a highly efficient method for compressing image data, for example.
The following is a description of the adaptive discrete cosine transform coding method(, or the ADCT method in short).
According to the ADCT method, images are divided into blocks comprising e.g. 8xc3x978 picture elements. DCT coefficients expressing the distribution of space frequencies are determined by performing two-dimensional discrete cosine transform (hereafter abbreviated as DCT) for the image signals from respective divided blocks. The image signals are coded by quantizing the DCT coefficients using thresholds corresponding to visions, according to a Huffman table obtained statistically from the quantized coefficients.
FIG. 1 is a block diagram of a coding circuit per the ADCT method.
FIG. 2 shows exemplary data for an original image received by the two-dimensional DCT unit.
FIG. 3 shows exemplary DCT coefficients representing a space frequency distribution.
The coding operation per the ADCT method is described below.
A two-dimensional DCT unit 24 receives from an input terminal 23 sixty-four (64) image signals, such as those shown in FIG. 2, for a black comprising 8xc3x978 picture elements. By orthogonally transforming the received image signals, the two-dimensional DCT unit 24 transforms them into coefficients having space frequency distributions such as those shown in FIG. 3, thereby calculating DCT coefficients, and outputs them to a linear quantizer 25.
FIG. 4 is a block diagram of the two-dimensional DCT unit 24. A one-dimensional DCT unit 30 performs one-dimensional DCTs for the image signals inputted from the input terminal 23, and a transposer 31 transposes the matrix obtained from the one-dimensional DCT unit 30. Then, a one-dimensional DCT unit 32 performs one dimensional DCTs, as with the one-dimensional DCT unit 30 described earlier. As with the transposer 31 described earlier, a transposer 33 transposes the matrix obtained at the one-dimensional DCT unit 32 and outputs it to a terminal 34. Through similar performances for all of image blocks, the inputted image signals are transformed to the DCT coefficients.
FIG. 5 is a table of thresholds for DCT coefficients in a block.
FIG. 6 is a table of exemplary quantized DCT coefficients.
Further explanation is made by referring back to FIG. 1. The linear quantizer 25 quantizes the inputted DCT coefficients by the quantization matrix comprising the optically determined thresholds shown in FIG. 5. The linear quantization produces quantized coefficients such as those shown in FIG. 6, which indicate that the DCT coefficients smaller than thresholds become 0, thereby forming quantized coefficients in which the quantized DC elements and only a few quantized AC coefficients have non-zero values.
Generally, the higher the visual sensitivities the lower the space frequencies are, and the lower the visual sensitivities the higher the space frequencies are. Therefore, as shown in FIG. 5, the absolute values of the quantization matrix elements, i.e. the thresholds for DCT coefficients corresponding to lower space frequencies, are smaller, and the absolute values corresponding to higher space frequencies are larger. Accordingly, as shown in FIG. 6, of quantized coefficients, only the quantized DC element at the top left end and a very few quantized AC coefficients representing low space frequency elements become significant coefficients having non-zero value values, whereas all others become insignificant coefficients, in most cases.
FIG. 7 shows the order of scanning the generated quantized coefficients (from the lower frequency elements to the higher frequency elements of the space frequencies).
The linear quantizer 25 transforms the two-dimensionally arrayed quantized coefficients into a one-dimensional form according to the zigzag scanning order shown in FIG. 7 and inputs them to a variable length coder 26 in the next stage.
Upon receipt of these quantized coefficients, the variable length coder 26 codes generated quantized coefficients by referring to a coding table 27 composed of a Huffman table created by statistical volumes for the respective images. As for their quantized DC elements, the differences between the current quantized DC coefficients and the previous quantized DC coefficients are coded in variable lengths. As for their quantized AC coefficients, the values of the quantized AC coefficients (hereafter referred to as indices) of significant coefficients (non-zero value coefficients) and the run lengths (hereafter referred to as runs) of the insignificant coefficients (zero value coefficients) are coded in variable lengths. The output terminal 28 sequentially outputs the coded data to the external units.
Meanwhile, the coded data obtained by the coding circuit per the ADCT method are reconstructed as images according to the following method.
FIG. 8 is a block diagram of a decoding circuit per ADCT method.
A variable length decoder 41 receives the coded data inputted from an input terminal 40. The variable length decoder 41 decodes the received coded data into fixed length data of the indices and runs and outputs the decoded data to a dequantizer 43, according to a decoding table 42 formed by a table inverse of the Huffman table composing the coding table 27.
On receiving the decoded data (the decoded quantized coefficients), the dequantizer 43 reconstructs the dequantized DCT coefficients through a dequantization by multiplying the respective decoded data by the thresholds stored at the corresponding positions in a quantization matrix 48. The dequantizer 43 outputs the dequantized DCT coefficients to a two-dimensional inverse DCT unit 44.
The two-dimensional inverse DCT unit 44 orthogonally transforms the received dequantized DCT coefficients indicating the distribution of the space frequencies into image signals.
The two-dimensional inverse DCT unit 44 is explained in further detail. FIG. 9 is a block diagram of a two-dimensional inverse DCT unit of the ADCT decoding circuit.
A one-dimensional inverse DCT unit 51 performs one-dimensional inverse DCTs for the DCT coefficients inputted from a terminal 50 and outputs them to a transposer 52. The transposer 52 transposes the matrix representing the outputs from the one-dimensional inverse DCT unit 51. A one-dimensional inverse DCT unit 53 again performs one-dimensional inverse DCTs on the transposed matrix obtained from the matrix transposition at the transposer 52. As with the transposer 52, a transposer 54 transposes the matrix representing the outputs from the one-dimensional inverse DCT unit 53. A terminal 45 outputs signals obtained by these processes, thereby reconstructing the images.
Per the earlier described ADCT method, the quantized coefficients are obtained by quantizing DCT coefficients by quantization thresholds. FIG. 10 is a block diagram of a conventional linear quantization circuit.
DCT coefficients inputted from a terminal 60 are supplied to a DCT coefficient receptor 64 to be stored. The DCT coefficient receptor 64 sequentially outputs the inputted DCT coefficients to a divider 65 upon receiving respective (RED) signals for reading data supplied from a timing controller 61.
Similarly, a quantization threshold storing unit 62 sequentially outputs the quantization thresholds corresponding to the respective stored data to the divider 65 upon receiving the respective (RED) signals for reading data supplied from a timing controller 61.
The divider 65 quantizes inputted DCT coefficients at the respective positions by the corresponding quantization thresholds, and outputs the results as quantized coefficients (QUD) to a latch 66. The timing controller 61 generates latch signals (LAT) for a latch 66 to latch quantized coefficients, and the latch 66 outputs quantized coefficients to a run/index judge 63, which judges, separates and outputs runs and indices. After one coefficient is quantized, the timing controller 61 instructs the DCT coefficient receptor 64 and the quantization threshold storing unit 62 to read the DCT coefficients and quantization thresholds at the next position for quantizing the DCT coefficient at the next position. By repeating the processes, comprising reading DCT coefficients stored in the DCT coefficient receptor 64 one by one, dividing them by the quantization thresholds stored in the quantization threshold storing unit 62, and outputting the results as quantized coefficients, for an entire image in block units, all the DCT coefficients for the image are quantized.
A variable length coder receives runs and indices separated from the quantized coefficients at the run/index judge 63. FIG. 11 shows the configuration of a variable length coder. A variable length coder 67 comprises a coding controller 69 and a code bit shifter 70. The coding controller 69 receives runs and indices, obtains coded signals by using a coding table 68, the Huffman table described earlier, and inputs them to the code bit shifter 70, which shifts the coded signals by the number of indicated bits and outputs them as coded data.
The conventional one-dimensional DCT units 51 and 53 shown in FIG. 9 reconstruct images in a column by performing inverse DCT operations represented by the matrix calculations expressed as equations 0 through 3 for the 8 picture elements in a column when a block comprises 8xc3x978 picture elements. In equations 0 through 8, column matrix elements X11 through X81 represent DCT coefficients in a column, column matrix elements Y11 through Y81 represent reconstructed image signals in a column, and square matrix elements A11 through A88 represent transform constants.                                                         Y11                                                          Y21                                                          Y31                                                          Y41                                                          Y51                                                          Y61                                                          Y71                                                          Y81                                      =                                                            A11                                            A12                                            A13                                            A14                                            A15                                            A16                                            A17                                            A18                                                                    A21                                            A22                                            A23                                            A24                                            A25                                            A26                                            A27                                            A28                                                                    A31                                            A32                                            A33                                            A34                                            A35                                            A36                                            A37                                            A38                                                                    A41                                            A42                                            A43                                            A44                                            A45                                            A46                                            A47                                            A48                                                                    A51                                            A52                                            A53                                            A54                                            A55                                            A56                                            A57                                            A58                                                                    A61                                            A62                                            A63                                            A64                                            A65                                            A66                                            A67                                            A68                                                                    A71                                            A72                                            A73                                            A74                                            A75                                            A76                                            A77                                            A78                                                                    A81                                            A82                                            A83                                            A84                                            A85                                            A86                                            A87                                            A88                                              ⁢                      xe2x80x83                    ⁢                                                    X11                                                                    X21                                                                    X31                                                                    X41                                                                    X51                                                                    X61                                                                    X71                                                                    X81                                                                        (                  equation          ⁢                      xe2x80x83                    ⁢          0                )                                                                    Y11              =                              xe2x80x83                            ⁢                                                A11                  *                  X11                                +                                  A12                  *                  X21                                +                                  A13                  *                  X31                                +                                  A14                  *                  X41                                +                                                                                                        xe2x80x83                            ⁢                                                A15                  *                  X51                                +                                  A16                  *                  X61                                +                                  A17                  *                  X71                                +                                  A18                  *                  X81                                                                                                        =                              xe2x80x83                            ⁢                              F11                +                F12                +                F13                +                F14                +                F15                +                F16                +                F17                +                F18                                                                        (                  equation          ⁢                      xe2x80x83                    ⁢          1                )                                                                    Y21              =                              xe2x80x83                            ⁢                                                A21                  *                  X11                                +                                  A22                  *                  X21                                +                                  A23                  *                  X31                                +                                  A24                  *                  X41                                +                                                                                                        xe2x80x83                            ⁢                                                A25                  *                  X51                                +                                  A26                  *                  X61                                +                                  A27                  *                  X71                                +                                  A28                  *                  X81                                                                                                        =                              xe2x80x83                            ⁢                              F21                +                F22                +                F23                +                F24                +                F25                +                F26                +                F27                +                F28                                                                        (                  equation          ⁢                      xe2x80x83                    ⁢          2                )                                                                    Y31              =                              xe2x80x83                            ⁢                                                A31                  *                  X11                                +                                  A32                  *                  X21                                +                                  A33                  *                  X31                                +                                  A34                  *                  X41                                +                                                                                                        xe2x80x83                            ⁢                                                A35                  *                  X51                                +                                  A36                  *                  X61                                +                                  A37                  *                  X71                                +                                  A38                  *                  X81                                                                                                        =                              xe2x80x83                            ⁢                              F31                +                F32                +                F33                +                F34                +                F35                +                F36                +                F37                +                F38                                                                        (                  equation          ⁢                      xe2x80x83                    ⁢          3                )                                                                    Y41              =                              xe2x80x83                            ⁢                                                A41                  *                  X11                                +                                  A42                  *                  X21                                +                                  A43                  *                  X31                                +                                  A44                  *                  X41                                +                                                                                                        xe2x80x83                            ⁢                                                A45                  *                  X51                                +                                  A46                  *                  X61                                +                                  A47                  *                  X71                                +                                  A48                  *                  X81                                                                                                        =                              xe2x80x83                            ⁢                              F41                +                F42                +                F43                +                F44                +                F45                +                F46                +                F47                +                F48                                                                        (                  equation          ⁢                      xe2x80x83                    ⁢          4                )                                                                    Y51              =                              xe2x80x83                            ⁢                                                A51                  *                  X11                                +                                  A52                  *                  X21                                +                                  A53                  *                  X31                                +                                  A54                  *                  X41                                +                                                                                                        xe2x80x83                            ⁢                                                A55                  *                  X51                                +                                  A56                  *                  X61                                +                                  A57                  *                  X71                                +                                  A58                  *                  X81                                                                                                        =                              xe2x80x83                            ⁢                              F51                +                F52                +                F53                +                F54                +                F55                +                F56                +                F57                +                F58                                                                        (                  equation          ⁢                      xe2x80x83                    ⁢          5                )                                                                    Y61              =                              xe2x80x83                            ⁢                                                A61                  *                  X11                                +                                  A62                  *                  X21                                +                                  A63                  *                  X31                                +                                  A64                  *                  X41                                +                                                                                                        xe2x80x83                            ⁢                                                A65                  *                  X51                                +                                  A66                  *                  X61                                +                                  A67                  *                  X71                                +                                  A68                  *                  X81                                                                                                        =                              xe2x80x83                            ⁢                              F61                +                F62                +                F63                +                F64                +                F65                +                F66                +                F67                +                F68                                                                        (                  equation          ⁢                      xe2x80x83                    ⁢          6                )                                                                    Y71              =                              xe2x80x83                            ⁢                                                A71                  *                  X11                                +                                  A72                  *                  X21                                +                                  A73                  *                  X31                                +                                  A74                  *                  X41                                +                                                                                                        xe2x80x83                            ⁢                                                A75                  *                  X51                                +                                  A76                  *                  X61                                +                                  A77                  *                  X71                                +                                  A78                  *                  X81                                                                                                        =                              xe2x80x83                            ⁢                              F71                +                F72                +                F73                +                F74                +                F75                +                F76                +                F77                +                F78                                                                        (                  equation          ⁢                      xe2x80x83                    ⁢          7                )                                                                    Y81              =                              xe2x80x83                            ⁢                                                A81                  *                  X11                                +                                  A82                  *                  X21                                +                                  A83                  *                  X31                                +                                  A84                  *                  X41                                +                                                                                                        xe2x80x83                            ⁢                                                A85                  *                  X51                                +                                  A86                  *                  X61                                +                                  A87                  *                  X71                                +                                  A88                  *                  X81                                                                                                        =                              xe2x80x83                            ⁢                              F81                +                F82                +                F83                +                F84                +                F85                +                F86                +                F87                +                F88                                                                        (                  equation          ⁢                      xe2x80x83                    ⁢          8                )            
A CPU conventionally codes and decodes image data as described earlier. That is, a CPU serially processes inputted image data and sequentially performs e.g. two-dimensional DCTs, linear quantizations, and coding or decoding in variable lengths in block units or image units. Hence, there are inherent problems of taking too much time in coding and decoding and of failing to process on a real time basis.
The problem of taking too much time is aggravated, since inverse DCTs are performed on DCT coefficients in all blocks when DCT coefficients are reconstructed as images.
Thus, the inverse DCTs for a block comprising 8xc3x978 picture elements are an 8xc3x978 matrix multiplication. Since each set of operations for a picture element comprises eight (8) multiplications between corresponding matrix elements and seven (7) additions of the eight (8) products, the calculations of product matrix for all 8xc3x978 picture elements in a block takes a total of 512 multiplications and 448 additions. This causes a problem that the inverse DCTs for all blocks in an image makes an image reconstruction hard to expedite.
Although it is possible to expedite the processing by forming the inverse DCT units 51 and 53 with eight sets of operation circuits, this makes the circuits of the inverse DCT units 51 and 53 larger, and hence the image reconstructing apparatus, too large.
This invention aims at realizing an image data coding and decoding apparatus which operates at high speed and an orthogonally transforming apparatus which enables small circuits to perform high speed processing.
This invention pertains to an image data reconstructing apparatus that decodes, dequantizes and performs two-dimensional inverse DCTs on the input codes obtained by coding after quantizing the results obtained by performing two-dimensional DCTs on image data for respective blocks each comprising Nxc3x97N picture elements. When there is a column whose elements are multiplied by 0, such an image data reconstructing apparatus skips the operations, thereby enabling small circuits to perform high speed processing. Before dequantizations, by respectively providing buffers for memorizing picture elements of two blocks before and after two-dimensional inverse DCTs, inputs and outputs are switched in block units to expedite the processes in pipeline operations.
Further, the circuit is made compact by forming a two-dimensional inverse DCT with two repetitions of a one-dimensional inverse DCT and of a matrix transposition. This is realized by storing the result of the one-dimensional inverse DCT in the buffer, thereby eliminating a matrix transposing circuit.